<!DOCTYPE html>
<html lang="zh-cn"><head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    
    <link href="/css/bootstrap.min.css" rel="stylesheet">
    <link href="/css/main.css" rel="stylesheet">

    <link rel="shortcut icon" type="image/x-icon" href="/img/favicon.ico" />

    <title>Go程序的递归函数 | wiseAI的小站</title>
</head><body><div class="container-fluid">
    <nav class="navbar fixed-top navbar-expand-sm navbar-dark bg-dark">
        <div class="container-fluid">
            <a class="navbar-brand" href="/">
                <img src="/img/favicon.ico" alt="" width="30" height="24" class="d-inline-block align-text-top">
                wiseAI的小站
            </a>
            <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
                <span class="navbar-toggler-icon"></span>
            </button>
            <div class="collapse navbar-collapse" id="navbarSupportedContent">
                <ul class="navbar-nav me-auto mb-2 mb-lg-0">
                    
                    <li class="nav-item">
                        <a  class="nav-link"   href="/articles/">文章</a>
                    </li>
                    
                    <li class="nav-item">
                        <a  class="nav-link"   href="/categories/">分类</a>
                    </li>
                    
                    <li class="nav-item">
                        <a  class="nav-link"   href="/tags/">关键字</a>
                    </li>
                    
                    <li class="nav-item">
                        <a  class="nav-link"   href="/post/golang/">golang编程</a>
                    </li>
                    
                    <li class="nav-item">
                        <a  class="nav-link"   href="/about/">关于</a>
                    </li>
                    
                </ul>
                <form class="d-flex">
                    <input id="search-query" class="form-control me-2" type="search" placeholder="Search for anything..." aria-label="Search">
                </form>
            </div>
        </div>
    </nav>
</div>




<div id="content">
<div class="container article">
	<h1>Go程序的递归函数</h1>
	<div class="post-meta">
		<div>
			
			
			By wiseai | 2022-07-22 | 2 minutes
		</div>
		<div class="tags">
			
			<a class="btn btn-light links btn-sm" href="/tags/%E7%BC%96%E7%A8%8B/">编程</a>
			
		</div>
	</div>
	<div>
		<div class="article-post">
			<h1 id="66-递归函数">6.6 递归函数</h1>
<p>当一个函数在其函数体内调用自身，则称之为递归。最经典的例子便是计算斐波那契数列，即前两个数为 1，从第三个数开始每个数均为前两个数之和。</p>
<p>数列如下所示：</p>
<pre><code>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
</code></pre>
<p>下面的程序可用于生成该数列（示例 6.13 <a href="examples/chapter_6/fibonacci.go">fibonacci.go</a>）：</p>
<pre tabindex="0"><code>package main

import &#34;fmt&#34;

func main() {
	result := 0
	for i := 0; i &lt;= 10; i++ {
		result = fibonacci(i)
		fmt.Printf(&#34;fibonacci(%d) is: %d\n&#34;, i, result)
	}
}

func fibonacci(n int) (res int) {
	if n &lt;= 1 {
		res = 1
	} else {
		res = fibonacci(n-1) + fibonacci(n-2)
	}
	return
}
</code></pre><p>输出：</p>
<pre tabindex="0"><code>fibonacci(0) is: 1
fibonacci(1) is: 1
fibonacci(2) is: 2
fibonacci(3) is: 3
fibonacci(4) is: 5
fibonacci(5) is: 8
fibonacci(6) is: 13
fibonacci(7) is: 21
fibonacci(8) is: 34
fibonacci(9) is: 55
fibonacci(10) is: 89
</code></pre><p>许多问题都可以使用优雅的递归来解决，比如说著名的快速排序算法。</p>
<p>在使用递归函数时经常会遇到的一个重要问题就是栈溢出：一般出现在大量的递归调用导致的程序栈内存分配耗尽。这个问题可以通过一个名为 <a href="https://zh.wikipedia.org/wiki/%E6%83%B0%E6%80%A7%E6%B1%82%E5%80%BC">懒惰求值</a> 的技术解决，在 Go 语言中，我们可以使用管道 (channel) 和 goroutine（详见<a href="14.8.md">第 14.8 节</a>）来实现。<a href="14.8.md">练习 14.12</a> 也会通过这个方案来优化斐波那契数列的生成问题。</p>
<p>Go 语言中也可以使用相互调用的递归函数：多个函数之间相互调用形成闭环。因为 Go 语言编译器的特殊性，这些函数的声明顺序可以是任意的。下面这个简单的例子展示了函数 <code>odd()</code> 和 <code>even()</code> 之间的相互调用（示例 6.14 <a href="examples/chapter_6/mut_recurs.go">mut_recurs.go</a>）：</p>
<pre tabindex="0"><code>package main

import (
	&#34;fmt&#34;
)

func main() {
	fmt.Printf(&#34;%d is even: is %t\n&#34;, 16, even(16)) // 16 is even: is true
	fmt.Printf(&#34;%d is odd: is %t\n&#34;, 17, odd(17))
	// 17 is odd: is true
	fmt.Printf(&#34;%d is odd: is %t\n&#34;, 18, odd(18))
	// 18 is odd: is false
}

func even(nr int) bool {
	if nr == 0 {
		return true
	}
	return odd(RevSign(nr) - 1)
}

func odd(nr int) bool {
	if nr == 0 {
		return false
	}
	return even(RevSign(nr) - 1)
}

func RevSign(nr int) int {
	if nr &lt; 0 {
		return -nr
	}
	return nr
}
</code></pre><h3 id="练习题">练习题</h3>
<p><strong>练习 6.4</strong> <a href="exercises/chapter_6/fibonacci2.go">fibonacci2.go</a></p>
<p>重写本节中生成斐波那契数列的程序并返回两个命名返回值（详见<a href="06.2.md">第 6.2 节</a>），即数列中的位置和对应的值，例如 5 与 4，89 与 10。</p>
<p><strong>练习 6.5</strong> <a href="exercises/chapter_6/10to1_recursive.go">10to1_recursive.go</a></p>
<p>使用递归函数从 10 打印到 1。</p>
<p><strong>练习 6.6</strong> <a href="exercises/chapter_6/factorial.go">factorial.go</a></p>
<p>实现一个输出前 30 个整数的阶乘的程序。</p>
<p>n 的阶乘定义为：<code>n! = n * (n-1)!, 0! = 1</code>，因此它非常适合使用递归函数来实现。</p>
<p>然后，使用命名返回值来实现这个程序的第二个版本。</p>
<p>特别注意的是，使用 <code>int</code> 类型最多只能计算到 12 的阶乘，因为一般情况下 <code>int</code> 类型的大小为 32 位，继续计算会导致溢出错误。那么，如何才能解决这个问题呢？</p>
<p>最好的解决方案就是使用 <code>big</code> 包（详见<a href="09.4.md">第 9.4 节</a>）。</p>

		</div>
	</div>
</div>


<div class="container">
    
    <div class="row">
        
        <div class="col-5">
            <a class="page-link link-dark text-end dh" href="/post/golang/2022.07.21-%E5%86%85%E7%BD%AE%E5%87%BD%E6%95%B0/">
                <h5>前一篇</h5><br>
                Go程序的内置函数
            </a>            
        </div>
        
        <div class="col-2">
        </div>
        
        <div class="col-5">
            <a class="page-link link-dark text-start dh" href="/post/golang/2022.07.23-%E5%B0%86%E5%87%BD%E6%95%B0%E4%BD%9C%E4%B8%BA%E5%8F%82%E6%95%B0/">
                <h5>后一篇</h5><br>
                Go程序中将函数作为参数
            </a>            
        </div>
        
    </div>
    
</div>

        </div><br><br>
<footer class="container">
    <h2>友情链接</h2>
    <hr>
    <nav class="nav nav-pills flex-column flex-sm-row">
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://wiseai.gitee.io/pages/gnzg/index.html" target="_blank">孤鸟之歌</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://wiseai.gitee.io/pages/mm/index.html" target="_blank">生成随机字符</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://wiseai.gitee.io/pages/md/index.html" target="_blank">MarkDown</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://gitee.com/" target="_blank">Gitee</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://github.com/" target="_blank">Github</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.aliyun.com/" target="_blank">阿里云</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://cloud.tencent.com/" target="_blank">腾讯云</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.oschina.net/" target="_blank">OSCHINA开源中国</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://gitee.com/wiseai/the-way-to-go_ZH_CN/blob/master/eBook/directory.md" target="_blank">the way to go</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://topgoer.com/" target="_blank">golang文档</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://goframe.org/display/gf" target="_blank">GoFrame</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.aliyundrive.com/" target="_blank">阿里云盘</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://cn.vuejs.org/" target="_blank">vue3文档</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://element-plus.gitee.io/zh-CN/" target="_blank">element-plus文档</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.runoob.com/vue3/vue3-tutorial.html" target="_blank">vue3菜鸟教程</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://v5.bootcss.com/" target="_blank">bootstrap v5 中文文档</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.bootstrap.cn/" target="_blank">bootstrap文档</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://caddy2.dengxiaolong.com/docs/" target="_blank">caddy中文教程</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.58pic.com/" target="_blank">千图</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://ifonts.com/" target="_blank">iFonts</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://marketing.qiniu.com/" target="_blank">七牛云</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.ixigua.com/" target="_blank">西瓜视频</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://wiseai.gitee.io/pages/yugang/index.html" target="_blank">鱼缸计算</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://justcc.mengkang.net/#/" target="_blank">C语言JustCC</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://wiseai.gitee.io/pages/pptist/" target="_blank">PPTist</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="/index.xml" target="_blank">RSS</a>
        
        <a class="flex-sm-fill text-sm-center nav-link links link-dark" href="https://www.kancloud.cn/idcpj/python/418553" target="_blank">参考资料</a>
        
    </nav>

    <div class="copyright text-center">
      <span class="power-by">
        Powered by <a class="links" href="https://gohugo.io" target="_blank">Hugo</a>
    </span>
    <span>|</span>
    <span>
        Theme - <a class="links" href="https://github.com/wiseai-go/blog-hugo" target="_blank">WiseAI</a>
    </span>
    <br>
    <span class="copyright-year">
        &copy;
        
        2017 -
        2023<span>
            陇ICP备15000157号
            
        </span></span>

</div>
</footer>
<script src="/js/bootstrap.bundle.min.js"></script>


</body>
</html>
